package code.oldCode.dynamic;

/**
 * @author cuihaoran
 * @date 2024/10/18
 */
public class OneDimension {

    /**
     * 2140. 解决智力问题
     *
     * @param questions
     * @return
     */
    public long mostPoints(int[][] questions) {
        // 第一反应是和官解1一样，但超时了O(n^2)，且更关键的是错了！
        // {{100, 5}, {1, 1}, {1, 2}, {1, 1}}应该输出100但输出了101！多贪心了状态！
        // 原因是所谓脑力恢复期，当遍历到最后一个{1, 1}的第一个{1, 1}时，
        // 看到他是100且脑力恢复期可以满足，
        // 但第一个{1, 1}之前的{100, 5}的脑力恢复期还没结束！
        // 要改的话需要加一个dp_time[]数组，把冷冻期也同步更新，懒得改了。
        int len = questions.length;
        // dp[i]为前i个问题能得到的最大分数
        // dp[i] = 遍历(j = 0~i-1)找到Max(dp[j]) + questions[i][0], 其中j + questions[j][1] < i
        long[] dp = new long[len];
        dp[0] = questions[0][0];
        for (int i = 1; i < len; i++) {
            long max = 0;
            for (int j = 0; j < i; j++) {
                if (j + questions[j][1] < i) {
                    max = Math.max(max, dp[j]);
                }
            }
            dp[i] = Math.max(dp[i - 1], max + questions[i][0]);
        }

        return dp[len - 1];
    }

    /**
     * 2140. 解决智力问题
     * 修改后的答案，修改dp[]的定义，但仍然超时
     */
    public long mostPoints_1(int[][] questions) {
        int len = questions.length;
        // dp[i]为选第i个问题能得到的最大分数
        // dp[i] = 遍历(j = 0~i-1)找到Max(dp[j]) + questions[i][0], 其中j + questions[j][1] < i
        int[] dp = new int[len];
        dp[0] = questions[0][0];
        int ans = dp[0];
        for (int i = 1; i < len; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                if (j + questions[j][1] < i) {
                    max = Math.max(max, dp[j]);
                }
            }
            dp[i] = max + questions[i][0];
            ans = Math.max(ans, dp[i]);
        }

        return ans;
    }

    /**
     * 2140. 解决智力问题 正解
     * @param questions
     * @return
     */
    public long mostPoints_SeiKai(int[][] questions) {
        // 上面的做法别扭的主要原因是，遍历的时候要考虑数组后面的内容
        // 所以只能再来遍历之前的，搞成了二重循环，复杂度为O(n^2)
        // 既然他关注后面的内容，那可以直接从后往前循环
        // dp[i]表示 第i道题目及之后的题目 获得的最大分数
        // dp[i] = Max(选i, 不选i) = Max(score[i] + dp[i + limit[i] + 1], dp[i + 1])
        // 这种思想叫“无后效性”
        int len = questions.length;
        long[] dp = new long[len];
        dp[len - 1] = questions[len - 1][0];
        for (int i = len - 2; i >= 0 ; i--) {
            if (i + questions[i][1] + 1 < len)
                dp[i] = Math.max(questions[i][0] + dp[i + questions[i][1] + 1], dp[i + 1]);
            else
                dp[i] = Math.max(questions[i][0], dp[i + 1]);
        }
        return dp[0];
    }


    public static void main(String[] args) {
        OneDimension oneDimension = new OneDimension();
        int[][] test = new int[][]{{100, 5}, {1, 1}, {1, 2}, {1, 1}};
        System.out.println(oneDimension.mostPoints(test));
    }
}
